{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Spiral Matrix II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #matrix #simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #矩阵 #模拟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: generateMatrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #螺旋矩阵 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个正整数 <code>n</code> ，生成一个包含 <code>1</code> 到 <code>n<sup>2</sup></code> 所有元素，且元素按顺时针顺序螺旋排列的 <code>n x n</code> 正方形矩阵 <code>matrix</code> 。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/11/13/spiraln.jpg\" style=\"width: 242px; height: 242px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 3\n",
    "<strong>输出：</strong>[[1,2,3],[8,9,4],[7,6,5]]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 1\n",
    "<strong>输出：</strong>[[1]]\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= n <= 20</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [spiral-matrix-ii](https://leetcode.cn/problems/spiral-matrix-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [spiral-matrix-ii](https://leetcode.cn/problems/spiral-matrix-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['3', '1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateMatrix(self, n: int) -> List[List[int]]:\n",
    "        matrix: List[List[int]] = [[0] * n for _ in range(n)]\n",
    "        last: int = n * n\n",
    "            \n",
    "        x: int = 0\n",
    "        y: int = 0\n",
    "        d: int = 0\n",
    "        dxdy: List[List[int]] = [[0, 1], [1, 0], [0, -1], [-1, 0]]\n",
    "        dx: int = dxdy[d][0]\n",
    "        dy: int = dxdy[d][1]\n",
    "        ends: List[List[int]] = [\n",
    "            [x, y + n], [x + n, y + n - 1],\n",
    "            [x + n - 1, y - 1], [x, y]\n",
    "        ]\n",
    "        dends: List[List[int]] = [[1, -1], [-1, -1], [-1, 1], [1, 1]]\n",
    "\n",
    "        i: int = 1\n",
    "        while i <= last:\n",
    "            matrix[x][y] = i\n",
    "            i += 1\n",
    "            \n",
    "            nx, ny = x + dx, y + dy\n",
    "            if [nx, ny] != ends[d]:\n",
    "                x, y = nx, ny\n",
    "            else:\n",
    "                ends[d][0] += dends[d][0]\n",
    "                ends[d][1] += dends[d][1]\n",
    "                d = (d + 1) % 4\n",
    "                dx, dy = dxdy[d]\n",
    "                x, y = x + dx, y + dy\n",
    "            \n",
    "        return matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateMatrix(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        return self.way2(n)\n",
    "    def way1(self,n):#不断旋转之前的元素 这个里面元组和列表类型不用转换 why\n",
    "        ans = [[n*n]]\n",
    "        while ans[0][0] > 1:\n",
    "            ans = [list(range(ans[0][0]-len(ans),ans[0][0]))] + list(zip(*ans[::-1]))\n",
    "        return ans\n",
    "    def way2(self,n):#walk the spiral\n",
    "        ans = [[0]*n for i in range(n)]\n",
    "        i, j = 0, 0#denote the current coordination\n",
    "        di, dj = 0, 1 #denote the direction of next move, if column is enough, row += 1\n",
    "        for k in range(n*n):\n",
    "            ans[i][j] = k+1\n",
    "            if ans[(i+di)%n][(j+dj)%n]: #tell us if we need to change the row\n",
    "                di, dj = dj, -di  #may be the signal of walking the spiral\n",
    "            i += di \n",
    "            j += dj\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateMatrix(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        res = [[0] * n for _ in range(n)]\n",
    "        cur, x, y, step = 0, -1, -1, n - 1\n",
    "        while True:\n",
    "            x += 1\n",
    "            y += 1\n",
    "            for _ in range(step):\n",
    "                cur += 1\n",
    "                res[x][y] = cur\n",
    "                y += 1\n",
    "            for _ in range(step):\n",
    "                cur += 1\n",
    "                res[x][y] = cur\n",
    "                x += 1\n",
    "            for _ in range(step):\n",
    "                cur += 1\n",
    "                res[x][y] = cur\n",
    "                y -= 1\n",
    "            for _ in range(step):\n",
    "                cur += 1\n",
    "                res[x][y] = cur\n",
    "                x -= 1\n",
    "            if step == 0:\n",
    "                res[x][y] = cur + 1\n",
    "            elif step < 0:\n",
    "                return res\n",
    "            step -= 2\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateMatrix(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        n-=1\n",
    "        self.matrix=[[0]*(n+1) for _ in range(n+1)]\n",
    "        self.start=1\n",
    "        def spiral(t):\n",
    "            for i in range(t,n-t):\n",
    "                self.matrix[t][i]=self.start\n",
    "                self.start+=1\n",
    "            for i in range(t,n-t):\n",
    "                self.matrix[i][n-t]=self.start\n",
    "                self.start+=1\n",
    "            for i in range(n-t,t,-1):\n",
    "                self.matrix[n-t][i]=self.start\n",
    "                self.start+=1\n",
    "            for i in range(n-t,t,-1):\n",
    "                self.matrix[i][t]=self.start\n",
    "                self.start+=1\n",
    "        if n%2==1:\n",
    "            for t in range(n//2+1):\n",
    "                spiral(t)\n",
    "        else:\n",
    "            for t in range(n//2):\n",
    "                spiral(t)\n",
    "            self.matrix[n//2][n//2]=(n+1)**2\n",
    "        return self.matrix\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateMatrix(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        num = 1\n",
    "        res = [[0 for _ in range(n)] for _ in range(n)]\n",
    "        rowtop, coleft, rowbot, colright = 0, 0, n-1, n-1\n",
    "        while rowbot > rowtop and coleft < colright:\n",
    "            for i in range(coleft, colright):\n",
    "                res[rowtop][i] = num\n",
    "                num += 1\n",
    "            for i in range(rowtop, rowbot):\n",
    "                res[i][colright] = num\n",
    "                num += 1\n",
    "            for i in range(colright, coleft, -1):\n",
    "                res[rowbot][i] = num\n",
    "                num += 1\n",
    "            for i in range(rowbot, rowtop, -1):\n",
    "                res[i][coleft] = num\n",
    "                num += 1\n",
    "            rowtop += 1\n",
    "            rowbot -= 1\n",
    "            coleft += 1\n",
    "            colright -= 1\n",
    "        if n % 2:\n",
    "            for i in range(coleft, colright+1):\n",
    "                res[rowtop][i] = num\n",
    "                num += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateMatrix(self, n: int) -> List[List[int]]:\n",
    "        matrix = [[0 for i in range(n)] for j in range(n)]\n",
    "        if n == 0:\n",
    "            return matrix\n",
    "        x1, x2, y1, y2 = 0, n-1, 0, n-1  #rowBegin, rowEnd, colBegin, colEnd\n",
    "        num = 1\n",
    "        while x1 <= x2 and y1 <= y2:\n",
    "            #向右遍历\n",
    "            for i in range(y1,y2+1):\n",
    "                matrix[x1][i] = num\n",
    "                num += 1\n",
    "            x1 += 1\n",
    "            #向下遍历\n",
    "            for i in range(x1,x2+1):\n",
    "                matrix[i][y2] = num\n",
    "                num += 1\n",
    "            y2 -= 1\n",
    "            if x1 <= x2:\n",
    "                #向左遍历\n",
    "                for i in range(y2,y1-1,-1):\n",
    "                    matrix[x2][i] = num\n",
    "                    num += 1\n",
    "            x2 -= 1\n",
    "            if y1 <= y2:\n",
    "                #向上遍历\n",
    "                for i in range(x2,x1-1,-1):\n",
    "                    matrix[i][y1] = num\n",
    "                    num += 1\n",
    "            y1 += 1   \n",
    "        return matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution(object):\n",
    "\n",
    "    def generateMatrix(self, n):\n",
    "\n",
    "        \"\"\"\n",
    "\n",
    "        :type n: int\n",
    "\n",
    "        :rtype: List[List[int]]\n",
    "\n",
    "        \"\"\"\n",
    "\n",
    "        ans = [[0] * n for _ in range(n)]\n",
    "\n",
    "        i = 0\n",
    "\n",
    "        j = 1\n",
    "\n",
    "        while j <= n*n:\n",
    "\n",
    "            for rightcol in range(i, n-i):\n",
    "\n",
    "                ans[i][rightcol] = j\n",
    "\n",
    "                j += 1\n",
    "\n",
    "            \n",
    "\n",
    "            downrow = -1\n",
    "\n",
    "            for downrow in range(i+1, n-i):\n",
    "\n",
    "                ans[downrow][rightcol] = j\n",
    "\n",
    "                j += 1\n",
    "\n",
    "            if downrow == -1:\n",
    "\n",
    "                break\n",
    "\n",
    "            icol = -1\n",
    "\n",
    "            for icol in range(rightcol-1, -1+i, -1):\n",
    "\n",
    "                ans[downrow][icol] = j\n",
    "\n",
    "                j += 1\n",
    "\n",
    "            if icol == -1:\n",
    "\n",
    "                break\n",
    "\n",
    "            for uprow in range(downrow-1, i, -1):\n",
    "\n",
    "                ans[uprow][icol] = j\n",
    "\n",
    "                j += 1\n",
    "\n",
    "            i += 1\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateMatrix(self,n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        temp = []\n",
    "        for i in range(n):\n",
    "            temp.append(0)\n",
    "        res = []\n",
    "        for i in range(n):\n",
    "            res.append(temp[:])\n",
    "        i = 1\n",
    "        j = 0\n",
    "        k = 0\n",
    "        flag = 1\n",
    "        while (i <= n * n):\n",
    "            if flag == 1:\n",
    "                res[j][k] = i\n",
    "                if k + 1 == n or res[j][k + 1] != 0:\n",
    "                    flag = 2\n",
    "                    j += 1\n",
    "                    i += 1\n",
    "                    continue\n",
    "                k += 1\n",
    "                i += 1\n",
    "                continue\n",
    "            if flag == 2:\n",
    "                res[j][k] = i\n",
    "                if j + 1 == n or res[j + 1][k] != 0:\n",
    "                    flag = 3\n",
    "                    k -= 1\n",
    "                    i += 1\n",
    "                    continue\n",
    "                j += 1\n",
    "                i += 1\n",
    "                continue\n",
    "            if flag == 3:\n",
    "                res[j][k] = i\n",
    "                if k - 1 == -1 or res[j][k - 1] != 0:\n",
    "                    flag = 4\n",
    "                    j -= 1\n",
    "                    i += 1\n",
    "                    continue\n",
    "                k -= 1\n",
    "                i += 1\n",
    "                continue\n",
    "            if flag == 4:\n",
    "                res[j][k] = i\n",
    "                if j - 1 == -1 or res[j - 1][k] != 0:\n",
    "                    flag = 1\n",
    "                    k += 1\n",
    "                    i += 1\n",
    "                    continue\n",
    "                j -= 1\n",
    "                i += 1\n",
    "                continue\n",
    "        return res\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateMatrix(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        A = [[0]*n for _ in range(n)]\n",
    "        i, j, di, dj = 0, 0, 0, 1\n",
    "        for k in range(1,n**2+1):\n",
    "            A[i][j] = k  \n",
    "            if A[(i+di)%n][(j+dj)%n]:\n",
    "                di, dj = dj, -di\n",
    "\n",
    "            i += di\n",
    "            j += dj\n",
    "            \n",
    "        return A\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateMatrix(self, n: int) -> List[List[int]]:\n",
    "        x1, y1 = 0, 0\n",
    "        x2, y2 = n - 1, n - 1\n",
    "        count = 1\n",
    "        res = [[0] * n for _ in range(n)]\n",
    "        while x1 <= x2 and y1 <= y2:\n",
    "            for i in range(y1, y2 + 1):\n",
    "                res[x1][i] = count\n",
    "                count += 1\n",
    "            for i in range(x1 + 1, x2 + 1):\n",
    "                res[i][y2] = count\n",
    "                count += 1\n",
    "            if x1 < x2 and y1 < y2:\n",
    "                for i in range(y2 - 1, y1 - 1, -1):\n",
    "                    res[x2][i] = count\n",
    "                    count += 1\n",
    "                for i in range(x2 - 1, x1, -1):\n",
    "                    res[i][y1] = count\n",
    "                    count += 1\n",
    "            x1 += 1\n",
    "            y1 += 1\n",
    "            x2 -= 1\n",
    "            y2 -= 1\n",
    "        return res\n",
    "                     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateMatrix(self, n: int) -> List[List[int]]:\n",
    "        d_x = [0, 1, 0, -1]\n",
    "        d_y = [1, 0, -1, 0]\n",
    "        result = [[0 for _ in range(n)] for _ in range(n)]\n",
    "        x = 0\n",
    "        y = 0\n",
    "        index = 0\n",
    "        for i in range(n * n):\n",
    "            result[x][y] = i + 1\n",
    "            a = x + d_x[index]\n",
    "            b = y + d_y[index]\n",
    "            if a == n or b == n or result[a][b] != 0:\n",
    "                index = (index + 1) % 4\n",
    "                x += d_x[index]\n",
    "                y += d_y[index]\n",
    "            else:\n",
    "                x = a\n",
    "                y = b\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateMatrix(self, n: int) -> List[List[int]]:\n",
    "        visited = [[False for _ in range(n)] for _ in range(n)]\n",
    "        dirt = [(0,1),(1,0),(0,-1),(-1,0)]\n",
    "        idd,r,c = 0,0,0\n",
    "        for i in range(n*n):\n",
    "                visited[r][c]=i+1\n",
    "                r0,c0 = r+dirt[idd][0],c+dirt[idd][1]\n",
    "                if r0>=n or r0<0 or c0>=n or c0<0 or visited[r0][c0]:\n",
    "                        idd+=1\n",
    "                        if idd==4: idd=0\n",
    "                        r0,c0 = r+dirt[idd][0],c+dirt[idd][1]\n",
    "                r,c = r0,c0\n",
    "        return visited"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateMatrix(self, n: int) -> List[List[int]]:\n",
    "        matrix=[]\n",
    "        for i in range(n):\n",
    "            matrix.append([0]*n)\n",
    "        i=0\n",
    "        j=0\n",
    "        sum_=0\n",
    "        direction=[1,0,0,0]\n",
    "        while True:\n",
    "            if sum_>=n*n:\n",
    "                break\n",
    "            sum_+=1\n",
    "            matrix[i][j]=sum_\n",
    "            if direction==[1,0,0,0]:  \n",
    "                if j+1<n and matrix[i][j+1]==0:\n",
    "                    j+=1\n",
    "                    continue\n",
    "                else:\n",
    "                    direction=[0,1,0,0]\n",
    "                    i+=1\n",
    "                    continue\n",
    "            \n",
    "            if direction==[0,1,0,0]:  \n",
    "                if i+1<n and matrix[i+1][j]==0:\n",
    "                    i+=1\n",
    "                    continue\n",
    "                else:\n",
    "                    direction=[0,0,1,0]\n",
    "                    j-=1\n",
    "                    continue\n",
    "            \n",
    "            if direction==[0,0,1,0]:  \n",
    "                if j-1>=0 and matrix[i][j-1]==0:\n",
    "                    j-=1\n",
    "                    continue\n",
    "                else:\n",
    "                    direction=[0,0,0,1]\n",
    "                    i-=1\n",
    "                    continue\n",
    "\n",
    "            if direction==[0,0,0,1]:  \n",
    "                if i-1>=0 and matrix[i-1][j]==0:\n",
    "                    i-=1\n",
    "                    continue\n",
    "                else:\n",
    "                    direction=[1,0,0,0]\n",
    "                    j+=1\n",
    "                    continue\n",
    "        return matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateMatrix(self, n: int) -> List[List[int]]:\n",
    "        def fillN(k, start_num):\n",
    "            ll = n - 2 * k\n",
    "            if ll == 1:\n",
    "                result[k][k] = start_num\n",
    "                return 1\n",
    "            array = list(range(start_num, start_num + 4 * (ll - 1)))\n",
    "            # print(array, ll, k)\n",
    "            result[k][k:k + ll] = array[0: ll]\n",
    "            for i in range(1, ll - 1):\n",
    "                result[k + i][k + ll - 1] = array[ll - 1 + i]\n",
    "            result[k + ll - 1][k:k + ll] = list(reversed(array[2 * ll - 2: 3 * ll - 2]))\n",
    "            for i in range(1, ll - 1):\n",
    "                result[k + i][k] = array[-i]\n",
    "            return 4 * (ll - 1)\n",
    "\n",
    "        result = [''] * n\n",
    "        for i in range(0, n):\n",
    "            result[i] = [''] * n\n",
    "\n",
    "        last_num = 0\n",
    "        mid = n // 2 - 1 + n % 2\n",
    "        for k in range(0, mid + 1):\n",
    "            count = fillN(k, last_num + 1)\n",
    "            last_num += count\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\tdef generateMatrix(self, n: int) -> [[int]]:\n",
    "\t\t# 上下左右边界\n",
    "\t\tl, r, t, b = 0, n - 1, 0, n - 1\n",
    "\t\tmat = [[0 for _ in range(n)] for _ in range(n)]\n",
    "\t\tnum, tar = 1, n * n\n",
    "\t\twhile num <= tar:\n",
    "\t\t\tfor i in range(l, r + 1):  # left to right\n",
    "\t\t\t\tmat[t][i] = num\n",
    "\t\t\t\tnum += 1\n",
    "\t\t\tt += 1\n",
    "\t\t\tfor i in range(t, b + 1):  # top to bottom\n",
    "\t\t\t\tmat[i][r] = num\n",
    "\t\t\t\tnum += 1\n",
    "\t\t\tr -= 1\n",
    "\t\t\tfor i in range(r, l - 1, -1):  # right to left\n",
    "\t\t\t\tmat[b][i] = num\n",
    "\t\t\t\tnum += 1\n",
    "\t\t\tb -= 1\n",
    "\t\t\tfor i in range(b, t - 1, -1):  # bottom to top\n",
    "\t\t\t\tmat[i][l] = num\n",
    "\t\t\t\tnum += 1\n",
    "\t\t\tl += 1\n",
    "\t\treturn mat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateMatrix(self, n: int) -> List[List[int]]:\n",
    "        ret = [ [0] * n for _ in range(n) ]\n",
    "        i, j = 0, 0\n",
    "        row_max, col_max = n - 1, n - 1\n",
    "        row_min, col_min = 0, 0\n",
    "        cur = 1  \n",
    "        while cur <= pow(n, 2):\n",
    "            ret[i][j] = cur\n",
    "            if i == row_min and j < col_max:\n",
    "                j += 1\n",
    "            elif j == col_max and i < row_max:\n",
    "                i += 1\n",
    "            elif i == row_max and j > col_min:\n",
    "                j -= 1\n",
    "                if j == col_min:\n",
    "                    row_min += 1\n",
    "                    row_max -= 1\n",
    "            elif j == col_min and i > row_min:\n",
    "                i -= 1    \n",
    "                if i == row_min:\n",
    "                    col_min += 1\n",
    "                    col_max -= 1            \n",
    "            cur += 1        \n",
    "        return ret            \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateMatrix(self, n: int) -> List[List[int]]:\n",
    "        result = [ [0 for j in range(n)] for i in range(n)]\n",
    "        left, right, top, bottom = 0, n-1, 0, n-1\n",
    "        start = 1\n",
    "        while left <= right and top <= bottom:\n",
    "            for column in range(left, right + 1):\n",
    "                result[top][column] = start\n",
    "                start += 1\n",
    "            for row in range(top + 1, bottom + 1):\n",
    "                result[row][right] = start\n",
    "                start += 1\n",
    "            if left < right and top < bottom:\n",
    "                for column in range(right - 1, left, -1):\n",
    "                    result[bottom][column] = start\n",
    "                    start += 1\n",
    "                for row in range(bottom, top, -1):\n",
    "                    result[row][left] = start\n",
    "                    start += 1\n",
    "            left, right, top, bottom = left + 1, right - 1, top + 1, bottom - 1\n",
    "        return result \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateMatrix(self, n: int) -> List[List[int]]:\n",
    "        res = [[0] * n for i in range(n)]\n",
    "        k = 0\n",
    "        for i in range(n, (n+1)//2, -1):\n",
    "            for j in range(n-i,i-1):\n",
    "                res[n-i][j] = k + j + 1\n",
    "                res[j][i-n-1] = k + j + 2 * i - n\n",
    "                res[i-n-1][-j-1] = k + j + 2 * (2 * i - n) - 1\n",
    "                res[-j-1][n-i] = k + j + 3 * (2 * i - n) - 2\n",
    "                # print(i,j,res)\n",
    "            k = k + j + 3 * (2 * i - n) - 3 - (n-i)\n",
    "        if n%2 == 1:\n",
    "            res[n//2][n//2] = n**2\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateMatrix(self, n: int) -> List[List[int]]:\n",
    "        matrix = [[None] * n for i in range(n)]\n",
    "        i = j = 0\n",
    "        status = 'R'\n",
    "        v = 0\n",
    "        while v < n * n:\n",
    "            v = v + 1\n",
    "            print(i,j,v)\n",
    "            matrix[i][j] = v\n",
    "            if status == 'R':\n",
    "                if j == n - 1 or matrix[i][j + 1]:\n",
    "                    if i == n - 1 or matrix[i + 1][j]:\n",
    "                        return matrix\n",
    "                    status = 'D'\n",
    "                    i = i + 1\n",
    "                else:\n",
    "                    j = j + 1\n",
    "            elif status == 'D':\n",
    "                if i == n - 1 or matrix[i + 1][j]:\n",
    "                    if j == 0 or matrix[i][j - 1]:\n",
    "                        return matrix\n",
    "                    status = 'L'\n",
    "                    j = j - 1\n",
    "                else:\n",
    "                    i = i + 1\n",
    "            elif status == 'L':\n",
    "                if j == 0 or matrix[i][j - 1]:\n",
    "                    if i == 0 or matrix[i - 1][j]:\n",
    "                        return matrix\n",
    "                    status = 'U'\n",
    "                    i = i - 1\n",
    "                else:\n",
    "                    j = j - 1\n",
    "            else:\n",
    "                if i == 0 or matrix[i - 1][j]:\n",
    "                    if i == n - 1 or matrix[i][j + 1]:\n",
    "                        return matrix\n",
    "                    status = 'R'\n",
    "                    j = j + 1\n",
    "                else:\n",
    "                    i = i - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateMatrix(self, n: int) -> List[List[int]]:\n",
    "\n",
    "        result = [[0]*n for _ in range(n)] \n",
    "\n",
    "        result[0][0] = 1 \n",
    "\n",
    "        visited = [[False]*n for _ in range(n)]\n",
    "\n",
    "        visited[0][0] = True\n",
    "\n",
    "        i,j,k = 0,0,1 \n",
    "        direction = 'right'\n",
    "\n",
    "        self.dfs(i,j,k,n,direction,visited,result) \n",
    "\n",
    "        return result \n",
    "\n",
    "    def dfs(self,i,j,k,n,direction,visited,result):\n",
    "        \n",
    "        print(i,j,k)\n",
    "        \n",
    "        if k == n * n:\n",
    "            return \n",
    "\n",
    "        if direction == 'right':\n",
    "            if j + 1 < n and visited[i][j+1] == False:\n",
    "                visited[i][j+1] = True \n",
    "                result[i][j+1] = k+1 \n",
    "                self.dfs(i,j+1,k+1,n,'right',visited,result) \n",
    "            else: \n",
    "                visited[i+1][j] = True\n",
    "                result[i+1][j] = k+1 \n",
    "                self.dfs(i+1,j,k+1,n,'down',visited,result)\n",
    "\n",
    "        if direction == 'down':\n",
    "            if i + 1 < n and visited[i+1][j] == False:\n",
    "                visited[i+1][j] = True\n",
    "                result[i+1][j] = k+1 \n",
    "                self.dfs(i+1,j,k+1,n,'down',visited,result)\n",
    "            else:\n",
    "                visited[i][j-1] = True \n",
    "                result[i][j-1] = k+1 \n",
    "                self.dfs(i,j-1,k+1,n,'left',visited,result) \n",
    "\n",
    "        if direction == 'left':\n",
    "            if j - 1 >= 0 and visited[i][j-1] == False: \n",
    "                visited[i][j-1] = True \n",
    "                result[i][j-1] = k+1 \n",
    "                self.dfs(i,j-1,k+1,n,'left',visited,result) \n",
    "            else:\n",
    "                visited[i-1][j] = True \n",
    "                result[i-1][j] = k+1\n",
    "                self.dfs(i-1,j,k+1,n,'up',visited,result)\n",
    "\n",
    "        if direction == 'up':\n",
    "            if i - 1 >= 0 and visited[i-1][j] == False:\n",
    "                visited[i-1][j] = True\n",
    "                result[i-1][j] = k+1\n",
    "                self.dfs(i-1,j,k+1,n,'up',visited,result)\n",
    "            else:\n",
    "                visited[i][j+1] = True \n",
    "                result[i][j+1] = k+1 \n",
    "                self.dfs(i,j+1,k+1,n,'right',visited,result) \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateMatrix(self, n: int) -> List[List[int]]:\n",
    "        \n",
    "        def solve(nums, steps, x, y, n, ans):\n",
    "            if nums:\n",
    "                ans[x][y] = nums[0]\n",
    "                nums = nums[1:]\n",
    "                for i, [stepx, stepy] in enumerate(steps):\n",
    "                    curx, cury = x + stepx, y + stepy\n",
    "                    if 0 <= curx < n and 0 <= cury < n and ans[curx][cury] == 0:\n",
    "                        cursteps = steps[i:] + steps[0:i]\n",
    "                        solve(nums, cursteps, curx, cury, n, ans)\n",
    "\n",
    "        ans = [[0 for _ in range(n)] for _ in range(n)]\n",
    "        nums = [i for i in range(1, n**2+1)]\n",
    "        steps = [(0,1), (1,0), (0, -1), (-1, 0)]\n",
    "        solve(nums, steps, 0, 0, n, ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateMatrix(self, n: int):\n",
    "\n",
    "        matrix = []\n",
    "        for x in range(n):\n",
    "            matrix.append([])\n",
    "            for y in range(n):\n",
    "                matrix[x].append(0)\n",
    "\n",
    "        def fill(bx,by,ex,ey,nu):\n",
    "            \n",
    "            if bx > ex or by > ey:\n",
    "                return\n",
    "\n",
    "            if bx == ex:\n",
    "                for x in range(by,ey+1):\n",
    "                    matrix[bx][x] = nu\n",
    "                    nu += 1\n",
    "                return\n",
    "\n",
    "            if by == ey:\n",
    "                for x in range(bx,ex+1):\n",
    "                    matrix[x][by] = nu\n",
    "                    nu += 1\n",
    "                return\n",
    "\n",
    "            for x in range(by,ey):\n",
    "                matrix[bx][x] = nu\n",
    "                nu += 1\n",
    "\n",
    "            for x in range(bx,ex):\n",
    "                matrix[x][ey] = nu\n",
    "                nu += 1\n",
    "\n",
    "\n",
    "            for x in range(ey,by,-1):\n",
    "                matrix[ex][x] = nu \n",
    "                nu += 1\n",
    "\n",
    "            for x in range(ex,bx,-1):\n",
    "                matrix[x][by] = nu\n",
    "                nu += 1\n",
    "\n",
    "            fill(bx+1,by+1,ex-1,ey-1,nu)\n",
    "\n",
    "\n",
    "        fill(0,0,n-1,n-1,1)\n",
    "\n",
    "        return matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateMatrix(self, n: int) -> List[List[int]]:\n",
    "        count=1\n",
    "        offset=0\n",
    "        startx = 0\n",
    "        starty = 0\n",
    "        i=0\n",
    "        j=0\n",
    "        nums= []\n",
    "        for i in range(n):\n",
    "            temp = list(range(n))\n",
    "            nums.append(temp)\n",
    "\n",
    "        for k in range(0,n//2):\n",
    "            for j in range(starty,n-1-offset):\n",
    "                nums[startx][j] = count\n",
    "                count=count+1\n",
    "            for i in range(startx,n-1-offset):\n",
    "                nums[i][j+1]=count\n",
    "                count=count+1\n",
    "            for j in range(n-1-offset,starty,-1):\n",
    "                nums[i+1][j]=count\n",
    "                count = count+1\n",
    "            for i in range(n-1-offset,startx,-1):\n",
    "                nums[i][j-1]=count\n",
    "                count=count+1\n",
    "            startx+=1\n",
    "            starty+=1\n",
    "            offset+=1\n",
    "        if (n%2==1):\n",
    "            nums[i][j]=count\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateMatrix(self, n: int) -> List[List[int]]:\n",
    "        nums = [[0] * n for i in range(n)]\n",
    "        startx, starty = 0, 0\n",
    "        loop, mid = n // 2, n // 2   # 迭代次数、n为奇数时，矩阵的中心点\n",
    "        count = 1  # 计数\n",
    "        for offest in range(1, loop + 1):\n",
    "            for i in range(starty, n - offest):  # 从左至右\n",
    "                nums[startx][i] = count\n",
    "                count += 1\n",
    "            for i in range(startx, n - offest):  # 从上至下\n",
    "                nums[i][n - offest] = count\n",
    "                count += 1\n",
    "            for i in range(n - offest, starty, -1):  # 从右至左\n",
    "                nums[n - offest][i] = count\n",
    "                count += 1\n",
    "            for i in range(n - offest, startx, -1): # 从下至上\n",
    "                nums[i][starty] = count\n",
    "                count += 1\n",
    "            startx += 1\n",
    "            starty += 1\n",
    "        if n % 2 != 0:\n",
    "            nums[mid][mid] = count\n",
    "        return nums\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateMatrix(self, n: int) -> List[List[int]]:\n",
    "        res = [[0] * n for _ in range(n)]\n",
    "        l,t = 0,0\n",
    "        r,b = n-1,n-1\n",
    "        tar = n*n\n",
    "        x = 1\n",
    "        while x<=tar:\n",
    "            for i in range(l,r+1):\n",
    "                res[t][i] = x\n",
    "                x += 1\n",
    "            t += 1\n",
    "            for i in range(t,b+1):\n",
    "                res[i][r] = x\n",
    "                x += 1\n",
    "            r -= 1\n",
    "            for i in range(r,l-1,-1):\n",
    "                res[b][i] = x\n",
    "                x += 1\n",
    "            b -= 1\n",
    "            for i in range(b,t-1,-1):\n",
    "                res[i][l] = x\n",
    "                x += 1\n",
    "            l += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateMatrix(self, n: int) -> List[List[int]]:\n",
    "        total = n * n\n",
    "        direction_index = 0\n",
    "        direction = ((0, 1), (1, 0), (0, -1), (-1, 0))\n",
    "        current_direction = direction[direction_index % 4]\n",
    "        val = 1\n",
    "        loc = [0, 0]\n",
    "        visited = set()\n",
    "        res = [[0 for _ in range(n)] for _ in range(n)]\n",
    "        ans = []\n",
    "        while val <= total:\n",
    "            \n",
    "            if 0 <= loc[0] < n and 0 <= loc[1] < n and (loc[0], loc[1]) not in visited:\n",
    "                print(loc, current_direction, val)\n",
    "                visited.add((loc[0], loc[1]))\n",
    "                res[loc[0]][loc[1]] = val\n",
    "                loc[0], loc[1] = loc[0] + current_direction[0], loc[1] + current_direction[1]\n",
    "                val += 1\n",
    "            else:\n",
    "                loc[0], loc[1] = loc[0] - current_direction[0], loc[1] - current_direction[1]\n",
    "                direction_index += 1\n",
    "                current_direction = direction[direction_index % 4]\n",
    "                loc[0], loc[1] = loc[0] + current_direction[0], loc[1] + current_direction[1]\n",
    "            \n",
    "        return res\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateMatrix(self, n: int) -> List[List[int]]:\n",
    "        nums = [[0]*n for _ in range(n)]\n",
    "        startx, starty = 0, 0\n",
    "        loop, mid = n // 2, n // 2\n",
    "        count = 1\n",
    "\n",
    "        for offset in range(1, loop + 1):\n",
    "            for i in range(starty, n - offset):\n",
    "                nums[startx][i] = count\n",
    "                count += 1\n",
    "            for i in range(startx, n - offset):\n",
    "                nums[i][n - offset] = count\n",
    "                count += 1\n",
    "            for i in range(n - offset, starty, -1):\n",
    "                nums[n - offset][i] = count\n",
    "                count += 1\n",
    "            for i in range(n - offset, startx, -1):\n",
    "                nums[i][starty] = count\n",
    "                count += 1\n",
    "            startx += 1\n",
    "            starty += 1\n",
    "        \n",
    "        if n % 2 != 0:\n",
    "            nums[mid][mid] = count\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateMatrix(self, n: int) -> List[List[int]]:\n",
    "        res = [[0]*n for _ in range(n)]\n",
    "        loop, mid = n // 2, n // 2\n",
    "        startx, starty = 0, 0\n",
    "        count = 1\n",
    "        for offset in range(1, loop+1):\n",
    "            for i in range(starty, n - offset):\n",
    "                res[startx][i] = count\n",
    "                count +=1\n",
    "            for i in range(startx, n - offset):\n",
    "                res[i][n-offset] = count\n",
    "                count +=1\n",
    "            for i in range(n-offset, starty, -1):\n",
    "                res[n-offset][i] = count \n",
    "                count +=1\n",
    "            for i in range(n-offset, startx, -1):\n",
    "                res[i][starty] = count\n",
    "                count +=1\n",
    "            startx +=1\n",
    "            starty +=1\n",
    "        if n %2  != 0:\n",
    "            res[mid][mid] = count\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def Spiral(x,y,start,n):\n",
    "    if n<=0:return\n",
    "    if n == 1:\n",
    "        a[x][y]=start\n",
    "        return\n",
    "    for j in range(x,x+n-1):\n",
    "        a[y][j] = start\n",
    "        start+=1\n",
    "    for i in range(y,y+n-1):\n",
    "        a[i][x+n-1]=start\n",
    "        start+=1\n",
    "    for j in range(x+n-1,x,-1):\n",
    "        a[y+n-1][j]=start\n",
    "        start+=1\n",
    "    for i in range(y+n-1,y,-1):\n",
    "        a[i][x]=start\n",
    "        start+=1\n",
    "    Spiral(x+1,y+1,start,n-2)\n",
    "class Solution:\n",
    "    def generateMatrix(self, n: int) -> List[List[int]]:\n",
    "        global a\n",
    "        a = [[0] * n for i in range(n) ]\n",
    "        Spiral(0,0,1,n)\n",
    "        return a\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateMatrix(self, n: int) -> List[List[int]]:\n",
    "        ans = [[0]*n for i in range(n)] #初始化二维列表\n",
    "        v = 0\n",
    "        for i in range(n // 2):\n",
    "            for j in range(i, n - i - 1):\n",
    "                v += 1\n",
    "                ans[i][j] = v\n",
    "            for j in range(i, n - i - 1):\n",
    "                v += 1\n",
    "                ans[j][n-i-1] = v\n",
    "            for j in range(n - i - 1, i, -1):\n",
    "                v += 1\n",
    "                ans[n-i-1][j] = v\n",
    "            for j in range(n - i - 1, i, -1):\n",
    "                v += 1\n",
    "                ans[j][i] = v\n",
    "        if n % 2 == 1:\n",
    "            v += 1\n",
    "            ans[n//2][n//2] = v\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
